1. Field of the Invention
The present invention relates to a system and method for providing paths in networks and more specifically, a system and method for executing service level agreements (SLAs) and provisioning for traffic flows in IP differentiated services networks and optical networks.
2. Background of the Invention
The prior art IP Differentiated Service (Diffserv) provides an efficient and scalable technique for providing Quality of Service (QoS) within the Internet. The prior art Diffserv is an improvement over the prior art per-flow signaling, which is unscalable due the per-flow state storage in the core network, to achieve end-to-end QoS guarantees. The prior art Diffserv technique overcomes the scalability problem of per-flow signaling by handling IP traffic as class-based aggregated flows, and differs from the prior art IntServ approach, which is based on application level flows.
In the Diffserv technique, each IP packet is categorized into one of a number of predefined Diffserv classes, and is assigned a service quality based on Diffserv class. Diffserv specifications can be implemented in a network area known as a Diffserv domain, which has edge elements where an IP packet can enter and exit the domain. A more detailed description of the Diffserv architecture is found in K. Kilkki, Differentiated Services for the Internet, 1999, which is incorporated herein by reference.
When the IP packet enters the domain at an edge element, the IP packet is classified at the edge element (e.g., ingress router), and marked with a Diffserv code point (DSCP) that identifies the Diffserv class of the entering IP packet. More specifically, the DSCP is encoded into the IP packet at the Class of Service/Type of Service (COS/TOS) field of the IP packet header. The IP packet is classified based on information extracted from the packet (e.g., layer-3 or layer-4).
Once the IP packet has been marked with the DSCP, the routers in the core of the Diffserv domain process the IP packet based on its Diffserv class. For example, the routers apply class-specific queuing, scheduling and routing within the core to satisfy the QoS guarantees for each Diffserv class.
However, this prior art classification system has various problems and disadvantages. For example, each Diffserv domain can individually define the scope of Diffserv classes and mechanisms by which the differentiated treatment is provided for different Diffserv classes. Thus, there is no standardization between Diffserv domains, as an IP packet may be classified and marked differently by ingress routers of different Diffserv domains.
To overcome the above-mentioned prior art problem, neighboring Diffserv domains can enter Service Level Agreements (SLAs) that can specify an amount of class-specific traffic that can be sent between domains. Class-specific policing is performed at the ingress router, and shaping is performed at the egress router to monitor and enforce the SLAs, which are discussed in greater detail below.
Further, IETF provides scheduling guidelines based on Per Hop Behavior (PHB) for a number of Diffserv classes, as disclosed in K. Nichols, S. Blake, F. Baker and D. Black, Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers, IETF Request for Comments 2474, December 1998, the contents of which is herein incorporated by reference.
For any domain for an ISP, class-specific scheduling and routing are used to meet the Diffserv class performance requirements. Routers have specific scheduling mechanisms based on class-specific PHBs. For example, the EF Diffserv class requires preemptive priority scheduling to secure an extremely low tolerance to queuing, while AF classes can be processed using Weighted Fair Queuing (WFQ) with appropriate scheduling weights. However, these scheduling mechanisms are static (i.e., non-adaptive), and once set on a router interface, cannot be adjusted to compensate for a varying traffic profile of a class, and will not change with changing traffic patterns in a class.
FIG. 1 illustrates a prior art inter-domain service level agreement (SLA). As noted above, SLAs can specify the aggregated amount of traffic that can enter a domain through an ingress router. As illustrated in FIG. 1, a SLA λ can specify the aggregated traffic from a first domain A to a second domain B via an ingress router I1 in the second domain B. The first domain A estimates the SLA rate from long-term traffic measurements and SLAs with other neighbor domains. The solid arrows illustrated in FIG. 1 represent traffic flows for this SLA, while other flows are represented as dotted arrows. Additionally, the SLA parameters are used for policing at ingress routers (e.g., I1) and shaping at egress routers (e.g., E3).
A more specific SLA can be provided for E3→I1 if the portions of the traffic λ that are travelling to different egress routers (e.g., E1, E2) can be specified. For example, the traffic from the first domain A that arrives at the second domain B via the ingress router I1 is expected to go through the egress routers E1, E2, and their respective rates λ1, λ2 can be specified in the SLA. Those respective rates are useful for Diffserv path provisioning. However, if the first domain A cannot estimate the fine-grain flow distribution, then the SLA will not contain this information, and the first domain A will have to estimate the fine-grain flow distribution from dynamic traffic measurement.
Each ingress router I1 of the second domain B uses the SLA information to compute the estimated volume of class-specific traffic between the ingress router I1 and all egress routers E1, E2 in the same domain, to create an N×N matrix M, where N represents the number of edge routers in the domain. The (ij)-th element of the traffic matrix for a given class represents the total bandwidth used by that given class from ingress router i to egress router j. For example, as illustrated in FIG. 1, for the second domain B, element (1,1) of the matrix M equals λ1, and element (1,2) of the matrix equals λ2. Once constructed, the traffic matrices are used to compute the provisioning routes (e.g., paths), for each non-zero element of those matrices, and the computed paths are pinned down using multi-protocol label switching (MPLS) for Diffserv networks or multi-protocol lambda switching (MPλS) for optical networks.
In the prior art example illustrated in FIG. 1, for the EF class, the peak rate λ of the specification is used in the traffic matrices, whereas for the AF class, the token bucket parameters are combined into a single rate parameter (e.g., equivalent bandwidth of an SLA specification) that can be used to construct the traffic matrix M. For example, the SLA rate information for each AF SLA illustrated in FIG. 1 can be specified as {λp,λm,B}, where λp is the peak bucket rate, λm is the mean bucket rate, and B is the maximum burst size. If an aggregated flow is allocated with its equivalent bandwidth and the flow complies with its SLA token bucket parameters, then the IP packets of that flow are guaranteed the QoS specified by the flow. Since the equivalent bandwidth also captures the loss requirements, the loss bounds are automatically guaranteed.
In addition to PHBs, class-specific routing is also used for end-to-end intra-domain QoS for the Diffserv classes, as IP packets with Diffserv markings can be forwarded using statically provisioned end-to-end paths. In K. Nichols, V. Jacobson, L. Zhang, A Two-bit Differentiated Services Architecture for the Internet, IETF Request for Comments 2638, July 1999, which is incorporated herein by reference, routes for provisioned paths are centrally computed using the Bandwidth Broker, or can be computed in a distributed manner.
In the prior art path provisioning system, splitting of individual flows is applied for balancing network loads. Although flow splitting may have the advantage of increasing the total bandwidth of accepted traffic flows, flow splitting also has a disadvantage in that ensuring packet ordering for individual micro-flows is difficult with splitting. For example, per-packet layer-3 lookup and hashing may be required at the ingress routers.
The Diffserv domain (or optical domain) can be described in terms of graph space. For example, consider a directed graph G=(N,E) with N nodes and E links. For each link e of the graph G, Ce represents link capacity, and Be represents the available bandwidth of the link, where Ce≧Be. Further, each element (i.e., traffic flow) of the traffic matrix (e.g., SLA matrix) is a triplet (r,s,d), where s is an ingress node, d is an egress node and r is traffic rate from ingress node s to egress node d. The triplets are referred to as T(i)=(ri, si, di,), where i=1, . . . , K and K is the total number of triplets (i.e., non-zero elements of traffic matrix). Some triplets (i.e., flows) may be accepted, and while other triplets may be rejected due to a lack of available bandwidth or available wavelengths for optical networks.
When provisioning paths with the above-described triplets, three criteria must be considered for optimal path provisioning. First, the flow blocking rate R is minimized according to Equation (1): R=R/K  (1)where R represents the number of rejected triplets T(j1), . . . ,T(jR), and K represented the total number of triplets.
Second, the traffic acceptance rate V is maximized according to Equations (2)-(4):
                              V          _                =                              V            /            W                    ⁢                                          ⁢          where                                    (        2        )                                V        =                              ∑                          i              ∉                              {                                                      J                    1                                    ,                  …                  ,                                      J                    R                                                  }                                              ⁢                                    r              i                        ⁢                                                  ⁢            and                                              (        3        )                                W        =                              ∑                          i              ∉                              {                                                      J                    1                                    ,                  …                  ,                                      J                    R                                                  }                                              ⁢                      r            i                                              (        4        )            V represents the total amount of bandwidth of accepted flows, and W represents the total amount of bandwidth of all flows.
Third, we minimize the hop-bandwidth product C according to Equation (5):
                    C        =                              ∑                          i              ∉                              {                                                      J                    1                                    ,                                                                          ,                                      J                    R                                                  }                                              ⁢                                    r              i                        ⁢                          h              i                                                          (        5        )            where hi is the number of hops in the path for the accepted triplet T(i) and as noted above, ri is the traffic rate for the accepted triplet.
The performance metrics R, V and C are conflicting targets: since flows have different bandwidth requirements, there is usually a choice of accepting fewer “large” flows at the expense of more “small” flows or vice versa. Further, because accepted bandwidth directly translates to the revenue earned by the ISP, the first priority is to maximize the traffic acceptance rate V by deciding which flows are accepted and which flows are rejected. The second priority is to minimize the hop-bandwidth product C.
To accomplish path provisioning, in the prior art naive algorithm (NA), the ith edge router first computes traffic vectors to the other (N−1) edge routers. Each traffic vector corresponds to the ith row of the traffic matrix (i.e., SLA information) of the domain. If the SLA information is not locally available at the ith edge router, a central SLA manager downloads the relevant SLA specifications to the ith edge router. Then, independently of other routers, each edge router computes and pins down the provisioning paths to all other edge routers in the domain.
To implement the NA, the prior art steps illustrated in FIG. 2 are performed. In a first step S1, a Diffserv class is selected, and triplets T(i) for the selected given class are listed in an arbitrary sequence. In a second step S2, a first triplet is selected from the arbitrary list. In a third step S3, all links where Be is less than ri (i.e., there is not enough bandwidth to use the link) are pruned to define a subnetwork, and in a fourth step S4, for the selected triplet T(i)=(ri, si, di), the minimum-hop path P is computed from si to di in the subnetwork that satisfies the current bandwidth availability of the network (i.e., Be>ri) for each link e in the path P. In a fifth step S5, it is determined whether the shortest path P exists. If the shortest path P does not exist, then T(i) is rejected in the sixth step S6. If the shortest path P exists, T(i) is accepted in the next step S7, and in the following step S8, Be is recomputed for each link e in the path P, and Be is adjusted as follows: Be=Be−ri. In the next step S9, the next triplet T(i) is selected from the list, and this prior art process is repeated. The NA may then be repeated for each class not yet selected.
The prior art NA is a benchmark for evaluating the benefits of using a centralized QoS server to handle path provisioning computations. The performance of the NA approximates that of distributed path provisioning, where edge routers select paths for their respective traffic flows independently of each other, and the bandwidth availability information is propagated to the routers by QOSPF protocol.
A QoS server can coordinate the order and manner of path selection. Some prior art work has been done on single path routing service in the context of telephone networks and virtual private network, as the routing algorithms used in these networks depend on specific switching equipment provided by manufacturers. For example, F. Lin and J. Wang, “A Minimax Utilization Routing Algorithm in Networks with Single-Path Routing,” Proceedings of IEEE Globecom'93. 1993, the contents of which is incorporated herein by reference, discuss the scenario use of single path routing to minimize the maximum link utilization factor. Lin and Wang describe this as a linear programming problem using Lagrangian Relaxation for obtaining suboptimal solutions.
The prior art QoS server-based algorithm referred to as an iterated sorting (IS) algorithm is illustrated in FIG. 3. In the prior art IS algorithm, the class is selected in a first step S10, as in the prior art NA. In a second step S11, the triplets are sorted in terms of the first field (i.e., the rate). It is assumed that the triplets T(i)=(ri, si, di) satisfy the condition r1≧rz≧ . . . ≧rk, where K is the total number of triplets with non-zero rates (i.e., SLA entries). The sorted list is then handled in the same manner as steps S2 through S9 of the prior art naive algorithm, in a third step S12.
In each iteration, the IS algorithm picks the largest (in terms of bandwidth required) flow from the list of non-rejected flows and attempts to fit the selected flow into the network. The algorithm may be suboptimal, as illustrated in FIG. 4. For example, all the links of the network illustrated in FIG. 4 have available capacity of 10 units, and there are only two triplets in the SLA: (6,5,6) and (5,1,4). Provisioning the path (5,2,3,6) for the first triplet (6,5,6) blocks the second triplet, (5,1,4). However, because of the sequential nature of the prior art algorithms, there is no mechanism to reverse the already provisioned paths. This is a problem inherent in the prior art IS and NA methods.
The prior art algorithms have various problems and disadvantages. As pointed out in C. Frei and B. Faltings, “Abstraction and Constraint Satisfaction Techniques for Planning Bandwidth Allocation”, Proceedings of IEEE Infocom, 2000, the contents of which is incorporated herein by reference, the path-provisioning problem is NP-hard and should be attacked by heuristic algorithms. The prior art naive algorithm and iterated sorting algorithms only provide sequential solutions, and do not disclose or suggest any other solution for the path-provisioning problem.